package com.zhang.study.chapter04;

/**
 * 在一个数组中，对于每个数num，求有多少个后面的数 * 2 依然<num，求总个数
 * 本题测试链接 : https://leetcode.cn/problems/reverse-pairs/description/
 **/
public class Code06_BiggerThanRightTwice {

    public int reversePairs(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int res = 0;
        int mergeSize = 1;
        while (mergeSize < nums.length) {
            int l = 0;
            while (l < nums.length) {
                int m = l + mergeSize - 1;
                if (m >= nums.length) {
                    break;
                }
                int r = Math.min(l + (mergeSize << 1) - 1, nums.length - 1);
                res += merge(nums, l, m, r);
                l = r + 1;
            }
            if (mergeSize > (nums.length >> 1)) {
                break;
            }
            mergeSize <<= 1;
        }
        return res;
    }

    private int merge(int[] nums, int l, int m, int r) {
        int res = 0;
        int indexR = m + 1;
        for (int i = l; i <= m; i++) {
            while (indexR <= r && ((long) nums[indexR] << 1) < (long)nums[i]) {
                indexR++;
            }
            res += indexR - (m + 1);
        }
        int[] temp = new int[r - l + 1];
        int i = 0;
        int j = l;
        int k = m + 1;
        while (j <= m && k <= r) {
            temp[i++] = nums[j] < nums[k] ? nums[j++] : nums[k++];
        }
        while (j <= m) {
            temp[i++] = nums[j++];
        }
        while (k <= r) {
            temp[i++] = nums[k++];
        }
        for (i = 0; i < temp.length; i++) {
            nums[l + i] = temp[i];
        }
        return res;
    }


}
